The invention relates generally to mass storage device interconnections and in particular, to a method and apparatus for increasing delivery bandwidth, providing fault tolerance, and input/output load balancing in a multiprocessor computer cluster.
Modern reliable computer systems require a large capacity mass storage, and large bandwidth access to that mass storage. While disk sizes have increased substantially, for example a typical personal computer today can be configured with over a gigabyte of storage, the bandwidth available to access the storage has improved, but not significantly. Thus, while large volumes of information can be stored, the rate at which the storage can be accessed has not generally changed in the past few years. In particular, considering the requirements of a digital video system for the delivery of constant bit rate video streams such as MPEG-2 digital video streams, it is important to provide a high bandwidth to accommodate the data requirements of the digital video network, for example an ATM OC-3 network interface.
While various methods have been employed to provide sufficient quantities of data in a reliable configuration, perhaps one of the more popular, and least expensive, approaches is the use of RAID-5 striping and parity techniques to organize data in a fault tolerant and efficient manner. The RAID (Redundant Array of Inexpensive Disks) approach is well described in the literature and has various levels of operation, including RAID-5, and the data organization can achieve data storage in a fault tolerant and load balanced manner.
In particular, RAID-5 provides that the stored data is spread among three or more disk drives, in a redundant manner, so that even if one of the disk drives fails, the data stored on the drive can be recovered in an efficient and error free manner from the other storage locations. This method also advantageously, using RAID-5 striping, makes use of each of the disk drives in relatively equal and substantially parallel operations. Accordingly, if one has a six gigabyte cluster volume which spans three disk drives, each disk drive would be responsible for servicing two gigabytes of the cluster volume. Each two gigabyte drive would be comprised of one-third redundant information, to provide the redundant, and thus fault tolerant, operation required for the RAID-5 approach.
Consider a processor reading a video data object from a local RAID-5 array. In normal operation, using a RAID-5 approach, when the processor needs to access a video data object which is spread across all of the disk drives connected to the processor, the processor reads a portion of the video data object in a round robin fashion from each of the disk drives. For example, a first 64 kilobyte block of the video data object can be stored and read on a first drive, the next 64 kilobyte block being stored on the second drive, and so on. In addition, however, the parity check (actually an EXCLUSIVE-OR function), also a 64 kilobyte block, is stored so that if there were n disk drives there would be one parity block written for each nxe2x88x921 blocks of data.
The processor reading the disk drives, however, is still xe2x80x9cstuckxe2x80x9d with a relatively narrow bandwidth. Accordingly, the amount of data which can be read is limited by the bus to which the drives are connected. For example, a SCSI bus which, while providing substantial improvements over buses from years ago, is still relatively slow compared to the needs of video applications. Also, the use of a local RAID-5 controller can combine the outputs of multiple local SCSI buses, but is subject to the failure of the local processor. Such a failure eliminates access to all the data.
Accordingly, objects of the invention are a method and apparatus having improved and increased mass storage read and write bandwidth (delivery bandwidth), operating using a reliable and fault tolerant protocol in a novel topology and enabling large quantities of data to be read and written in accordance with well known and accepted techniques. Other objects of the invention include a method and apparatus which is relatively inexpensive, reliable, simple to build, and easy to maintain.
The invention relates to a method and apparatus for redundantly storing data in a distributed computer system having at least three processor systems, each processor system having at least one central processing unit and at least one mass storage sub-system. The method features the steps of interconnecting each one of the processor systems in a point to point two way channel interconnection with each other one of the processor systems and storing input data across the processor systems according to a distributed, redundant storage process. Thereby, data is stored at each mass sub-storage system and some of a redundant representation of the data is stored also at each processor mass storage sub-system.
In particular aspects of the invention, the method features storing data across the processor systems according to a RAID-5 process and, further, storing data within each processor system according to a RAID-5 process.
The method further features the step of reading data from the computer system, in the absence of a failure of any of the processor systems, over respective ones of the data channel interconnections, whereby the reading step establishes a load balance across the processor systems. In the presence of a failure of one of the processor systems, the reading of data from the computer system features the steps of reading data from each non-failed processor system storing the data, and reading redundant data from the non-failed processor systems in place of the data stored at the failed processor system. Thereafter, the needed data stored at the failed processor system can be recreated using the redundant data and the data read from the non-failed processor systems. In some embodiments of the invention, during the time when a failure has occurred at any processor system, the method may prevent the writing of any data at any processor system until the failed processor system is brought back on line.
In another aspect, the invention further features the limiting case wherein there are only two processor systems initially. In accordance with this aspect of the invention, the system continues, in the absence of a failure, to provide increased bandwidth by reading succeeding blocks of data from alternate processors in sequence; and, in this manner, effects a load balancing and provides increased read bandwidth compared to a typical so-called xe2x80x9cmirroredxe2x80x9d system. In a typical mirrored system, data is read from one processor only, the other processor acting as a backup. Thus, in accordance with the invention, data is read from all of the processors thereby providing an increased read bandwidth and load balancing. As noted hereinafter, therefore, the two processor version of the invention, while not providing all of the advantages of the system with a larger number of processors, does allow easy scalability to a processor system having greater capacity, less overhead, and greater bandwidth.
In various aspects of the storage step, the method, in some embodiments of the invention wherein data storage is modelled at a disk abstraction level, feature either designating one processor system to effect all write functions for the computer system, designating one processor for allocating files for each data input and enabling all processor systems to write input data to each of its associated and allocated files, or arbitrating write operations among the processor systems using a distributed lock manager.
In another aspect of the storage step, however, the data input is stored as named fragment files, or named files, in each processor system. When stored as named fragment files, or named files, they can be accessed and reconstructed, for example even when a process or system is added to the distributed computer system. The system continues to deliver stored data as an output stream even as the number of processor systems, network interfaces, and amount of storage is changed. This is possible because the method uses file names to distinguish, modulus xe2x80x9cNxe2x80x9d, data fragments from modulus xe2x80x9cN+1xe2x80x9d data fragments, even as these modulus xe2x80x9cN+1xe2x80x9d data fragments are created from the modulus xe2x80x9cNxe2x80x9d fragments. Further, the method features the step of reconstructing a failed processor system by reconstructing only the data objects which were written while the processor system was in a failed state.
The distributed computer system in accordance with the invention has at least three processor systems for redundantly storing data, each processor system having at least one central processing unit and at least one mass storage system. The distributed computer system features interconnecting channels providing a point to point two way channel interconnection from each one of the processor systems to each other one of the processor systems, and a data storage controller at each processor system. The controllers act to store data input at any one of the processor systems according to a distributed redundant storage process whereby data is stored at each of the computer processors and some of a redundant representation of the data is stored also at each of the processors. In a preferred embodiment, the storage controllers store data across the processing systems according to a RAID-5 process, and further, can store data at each processor system in its associated mass storage sub-system according to a RAID-5 process.
The apparatus of the invention further features a system in which the controllers read data from the computer system, in the absence of a failure of any processor system, so as to maintain and establish a load balance across the computer system. In the presence of a failure of one of the processor systems, the controllers read data from each non-failed processor system storing the data (over the appropriate dedicated network connection) and read redundant data from each non-failed processor system in place of the data stored at the failed processor system. The requesting processor system can then recreate the data stored at the failed processor using the read data and the redundant data. In a preferred embodiment, an xe2x80x9cexternalxe2x80x9d processor can be employed to recreate the data stored at the failed processor, thereby preserving the delivery bandwidth of the system even in the face of a failed processor.
In another aspect, the apparatus features a storage controller which stores the input data as named fragment files, or named files, in the distributed computer system.
The apparatus of the invention also relates to a redundant switch having at least n interruptible inputs, n interrupting inputs, and n outputs. The redundant switch features n+1 switched systems, each switched system having at least two control inputs, a first input, a second input, a third input, and a fourth input, and a first and a second output. Each switched system is connected at its second output to n interrupting signal generator, n interrupting output of the associated signal generator being connected to the second input of the connected switched system. The switched systems are interconnected in a ring structure so that each switched system further has n interruptible input signal connected to the first input, the second input of a first neighbor switched system in the ring being connected to the third input, the interruptible input from the other neighbor switched system on the ring being connected to the fourth input, and each switched system having switching circuitry responsive to the control input for switching any of its inputs to at least its first output and for connecting either of its first and fourth inputs to its second output. The controller provides the control signals to the control inputs of the switched system to enable the cross-bar operation.
In another aspect, the redundant switch has n+1 switched systems each switched system having at least two control inputs, four signal inputs, and two signal outputs. Each switched system is connected at one of its outputs to an associated interrupting signal generator and n interrupting output of the associated signal generator is connected to an input of the connected switched system. The switched systems are interconnected in a ring structure so that each switched system is connected to a first and a second nearest neighbor. Each switched system has switching circuitry responsive to the control input for the switched system for selectively switching its inputs to its outputs. A controller provides the control inputs to the switched systems to enable the switched systems to effectively rotate signal switching functions one position in one or both directions around the ring. Thereby, a failed signal generator can be bypassed and the signals on the n first outputs continue uninterrupted.
In another aspect, the invention relates to a distributed data delivery system having at least three processor systems for redundantly storing data, each processor system having at least one central processing unit and one mass storage system. Interconnecting data channels provide a point to point, two way, channel interconnection from each one of the processor systems to each other one of the processor systems. A data storage controller at each processor system stores data input from any one of the processor systems according to a distributed, redundant storage process whereby data is stored at each of the processor systems and some of a redundant representation of the data is stored at each of the processors as well. A switching circuit having n interruptible input ports, at least n+1 interrupting input ports, and at least n+1 output ports, has n interruptible input signals connected to respective primary processor systems, each primary processor system having an output connected to a respective interrupting input. A switching controller, connected to the switching circuit for selectively interrupting each of the n interruptible input ports with the signal information available from a respective one of the processor systems, in the event of a failure at a processor, and using a previously unused processor system in that process, causes the switching circuit to connect the interruptible input port of the failed processor system to a different processor system, and to replace the output of the failed processor system with the output of another processor system.